package io.zhengsh.vvip.leetcode.twopointer;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Q13_3Num {

    class Solution {
        public List<List<Integer>> threeSum(int[] nums) {
            int n = nums.length;
            Arrays.sort(nums);
            List<List<Integer>> ans = new ArrayList<>();
            // 循环
            for (int first = 0; first < n; first++) {
                // 需要和上次的值不同
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }

                // c 指向数组的最右端指针
                int third = n - 1;
                int target = -nums[first];
                // 循环
                for (int second = first + 1; second < n; second++) {
                    // 需要和上次的值不同
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }

                    // 保证 b 在 c 的左侧
                    while (second < third && nums[second] + nums[third] > target) {
                        --third;
                    }

                    // 指针
                    if (second == third) {
                        break;
                    }

                    if (nums[second] + nums[third] == target) {
                        ans.add(Arrays.asList(nums[first], nums[second], nums[third]));
                    }
                }
            }
            return ans;
        }
    }
}
